1. Field of the Invention
The present invention relates to an image processing apparatus, an image processing method, and a computer-readable medium which vectorize a color image. The present invention more particularly relates to a technique of extracting a boundary line common to color regions from a contour coordinate point array when a color region (a region formed from pixels that can be regarded as having the same color) includes an 8-neighbor connection.
2. Description of the Related Art
A method of extracting contour information (Japanese Patent No. 3026592) and a method of approximating a coordinate point array by a given function (Japanese Patent No. 4378208) have been proposed as techniques associated with image vectorization which assumes a text as a target. Further, vectorization for a line image (Japanese Patent Laid-Open No. 2007-293829) and vectorization for a color image (Japanese Patent Laid-Open No. 2006-344069), for example, have been proposed as techniques of vectorization processing for various types of images assuming general illustration images as targets.
Vectorized data allows smooth contour representation free from jaggies even when it is scaled to a desired size. Also, vectorized data has an effect of reducing the data size in, for example, an illustration image, thus offering an advantage in facilitating, for example, editing processing on a computer. An image such as a text or a line image can often be processed as a binary or monochrome image, so a preferable vectorization result can be obtained for this image when a contour extracted for each color connection region (each set of pixels having the same color) is approximated by a given function. However, an illustration often has a multiple of colors, so a method of processing the boundary line between neighboring color regions must be devised in that case. When, for example, processing compatible with a binary image is directly applied to a multilevel image, a contour (boundary line) is extracted for each color region, and the contour (boundary line) is approximated by a given function for each of the extracted color regions. Unfortunately, when the boundary line between neighboring color regions is approximated by a given function individually for each color region, two different approximation curves are obtained for one boundary line due to an approximation error, thus generating a gap or an overlap between them. FIGS. 3A and 3B show this problem. FIG. 3A illustrates an example in which the contour shapes of color regions are extracted from an input image. Three neighboring color regions (having boundary lines shared with other regions) are present, assuming that the white background is excluded. FIG. 3B shows the result of processing of approximating contour information shown in FIG. 3A by a given function individually for each color region, in which a gap and/or an overlap is generated between color regions.
In view of the above-mentioned problem, a vectorization method which generates no gap between color regions has also been proposed. In, for example, Japanese Patent Laid-Open No. 2006-031245, the boundary between pixels having a color difference equal to or larger than a predetermined threshold is traced as a contour, and the tracing path is branched every time it reaches an intersection point of color regions, thereby repeatedly searching for the contour. A partial contour segmented between intersection points of color regions is approximated by a given function upon defining it as the unit of processing of function approximation, and data after function approximation are concatenated together, thereby generating vector data. Therefore, an approximation result common to boundary lines is applied, so neither a gap nor an overlap is generated between them in principle.
In general, two concepts are available for the pixel connection state. The first concept is a 4-neighbor connection (4-connectivity), in which when pixels in four directions: the upward, downward, leftward, and rightward directions upon defining a pixel of interest as their center are searched, and a pixel having the same color as the pixel of interest is detected, the detected pixel and the pixel of interest are regarded as being connected to each other. The second concept is an 8-neighbor connection (8-connectivity), in which when pixels in eight directions: the upward, downward, leftward, rightward, and oblique directions upon defining a pixel of interest as their center are searched, and a pixel having the same color as the pixel of interest is detected, the detected pixel and the pixel of interest are regarded as being connected to each other. Contours can be classified into a contour (to be referred to as an outside contour hereinafter) which forms the external boundary between regions, and a contour (to be referred to as an inside contour hereinafter) which forms the internal boundary between these regions. Note that when an image includes a pixel set having an 8-neighbor connection, which includes a portion in which neighboring pixels are connected only in an oblique direction, the following problem is posed when the contour of a region having the pixel set is extracted. An outside contour extracted upon defining the pixel set as that having an 8-neighbor connection becomes one outside contour, including the portion in which neighboring pixels are connected only in an oblique direction. On the other hand, an inside contour extracted upon defining another pixel set neighboring the outside of the pixel set as that having an 8-neighbor connection becomes a set of two inside contours as it is cut in the portion in which neighboring pixels are connected only in an oblique direction. That is, an outside contour extracted based on a first pixel set which includes a portion in which neighboring pixels are connected only in an oblique direction, and an inside contour extracted based on a second pixel set which surrounds the first pixel set, have different shapes. This makes it difficult to identify a boundary line common to pixel sets.
FIGS. 4A and 4B show the difference in contour extraction result due to factors associated with the connection characteristics between a 4-neighbor connection and an 8-neighbor connection. Seven gray pixels (hatched portions) are connected by a 4-neighbor connection in FIG. 4A, while five gray pixels are connected by an 8-neighbor connection in FIG. 4B. When a color contour shown in FIG. 4A is extracted, the inside contour of white pixels coincides with the outside contour of gray pixels regardless of whether the concept of a 4-neighbor connection or an 8-neighbor connection is adopted. However, in case of FIG. 4B, when the inside contour of white pixels and the outside contour of gray pixels are extracted based on the concept of a 4-neighbor connection, the inside contour of white pixels is extracted as one continuous coordinate point array (one inside contour), while the outside contour of gray pixels is extracted as three coordinate point arrays (three outside contours) because it is determined that this outside contour is not continuous in a portion in which neighboring pixels are connected only in an oblique direction. Also, when the inside contour of white pixels and the outside contour of gray pixels are extracted based on the concept of an 8-neighbor connection, the outside contour of gray pixels is extracted as one coordinate point array (one outside contour), while the inside contour of white pixels is extracted as three coordinate point arrays (three inside contours) because it is determined that this inside contour is continuous in a portion neighboring only in an oblique direction. In this case, when a common boundary line is to be extracted, the differences in number of loops which form a contour and in number of coordinate points included in each loop pose a problem, thus making it very difficult to identify a common boundary line. Japanese Patent No. 3026592 discloses no method of solving this problem.
To combat this situation, each of a coordinate point array extracted as an outside contour and that extracted as an inside contour can be cut in a portion in which neighboring pixels are connected only in an oblique direction, and compare the cut coordinate point arrays as boundary lines. However, when a fine line having an 8-neighbor connection is input as an input image as shown in FIG. 5, the boundary line is finely cut in a portion in which neighboring pixels are connected in an oblique direction. Then, when each cut contour is individually approximated by a given function and vectorized, the image quality of vector data output as a vectorization result considerably degrades.